package leetcode.interviewClassics;

import leetcode.ListNode;

/**
 * @author Cheng Jun
 * Description: 找出 链表倒数 第k个 节点
 * @version 1.0
 * @date 2021/11/1 17:33
 */
public class kthToLast {

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(1, null);
        ListNode listNode4 = new ListNode(2, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(3, listNode3);
        ListNode listNode1 = new ListNode(2, listNode2);
        ListNode listNode0 = new ListNode(1, listNode1);
        // System.out.println(kthToLast(listNode0, 2));
        System.out.println(kthToLast1(listNode0, 2));
    }

    // 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
    static int kthToLast(ListNode head, int k) {
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            size++;
        }
        int number = size + 1 - k;
        int index = 1;
        while (head != null) {

            if (index == number) {
                return head.val;
            }
            head = head.next;
            index++;
        }
        return 0;
    }

    // 双指针 相差 k 步
    static int kthToLast1(ListNode head, int k) {
        ListNode first = head;
        ListNode second = head;
        while (k-- != 0) {
            first = first.next;
        }
        while (first != null) {
            second = second.next;
            first = first.next;
        }
        return second.val;
    }
}
